package com.shm.leetcode;

/**
 * 605. 种花问题
 * 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
 *
 * 给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
 *
 * 示例 1:
 *
 * 输入: flowerbed = [1,0,0,0,1], n = 1
 * 输出: True
 * 示例 2:
 *
 * 输入: flowerbed = [1,0,0,0,1], n = 2
 * 输出: False
 * 注意:
 *
 * 数组内已种好的花不会违反种植规则。
 * 输入的数组长度范围为 [1, 20000]。
 * n 是非负整数，且不会超过输入数组的大小。
 * @author SHM
 */
public class CanPlaceFlowers {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int len = flowerbed.length;
        if(len==1&&flowerbed[0]==0&&n<=1){
            return true;
        }
        //可种花的数量
        int cnt = 0;
        for(int i=0;i<len;i++){
            //由于只需要判断能否在不打破种植规则的情况下在花坛内种入 nn 朵花，不需要具体知道最多可以在花坛内种入多少朵花，因此可以在循环内进行优化，当可以种入的花的数量已经达到 nn，则可以直接返回 \text{true}true，不需要继续计算数组剩下的部分。
            if(cnt>=n){
                return true;
            }
            //头部是否可种花
            if(i==0&&flowerbed[i]==0&&flowerbed[i+1]==0){
                cnt++;
                //置为已种花
                flowerbed[i]=1;
            }
            //尾部是否可种花
            if(i==len-1&&flowerbed[i]==0&&flowerbed[i-1]==0){
                cnt++;
                flowerbed[i]=1;
            } else if(i>0&&flowerbed[i]==0&&flowerbed[i-1]==0&&flowerbed[i+1]==0){
                //其他位置
                cnt++;
                flowerbed[i]=1;
            }
        }
        return cnt>=n;
    }

    /**
     * 解题思路
     * 首先这里我用的是连跳两格的方法，因为如果遇到1,那么下一格子一定是0，这是毋庸置疑的（规则限定），所以如果遇到最后一个格子，或者下个格子不是1，果断填充
     *
     * 作者：heroding
     * 链接：https://leetcode-cn.com/problems/can-place-flowers/solution/qi-si-miao-jie-by-heroding-h7m0/
     *
     * @param flowerbed
     * @param n
     * @return
     */
    public boolean canPlaceFlowers_2(int[] flowerbed, int n) {
        // 每次跳两格
        for (int i = 0; i < flowerbed.length; i += 2) {
            // 如果当前为空地
            if (flowerbed[i] == 0) {
                // 如果是最后一格或者下一格为空
                if (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {
                    n--;
                } else {
                    i++;
                }
            }
            if (n<=0){
                return true;
            }
        }
        return n <= 0;
    }
}
